package com.itheima.leetcode.od.b.binary;

import com.itheima.algorithm.dynamicprogramming.Leetcode300;

import java.util.Arrays;

/**
 * (B卷,200分)- 书籍叠放（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 书籍的长、宽都是整数对应 (l,w)。如果书A的长宽度都比B长宽大时，则允许将B排列放在A上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。
 * <p>
 * 输入描述
 * <p>
 * 输入：books = [[20,16],[15,11],[10,10],[9,10]]
 * <p>
 * 说明：总共4本书籍，第一本长度为20宽度为16；第二本书长度为15宽度为11，依次类推，最后一本书长度为9宽度为10.
 * <p>
 * 输出描述
 * <p>
 * 输出：3
 * <p>
 * 说明: 最多3个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]
 * <p>
 * 用例
 * <p>
 * 输入	[[20,16],[15,11],[10,10],[9,10]]
 * 输出	3
 * <p>
 * 题目解析
 * <p>
 * 本题就是LeetCode - 354 俄罗斯套娃信封问题_伏城之外的博客-CSDN博客
 * <p>
 * 可以采用耐心排序+二分查找，实现O(nlgn)时间复杂度的算法。
 * <p>
 * 具体解题思路请看上面博客。
 */
public class StackingBooks {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();*/

//        String input = "[[20,16],[15,11],[10,10],[9,10]]";
        String input = "[[13,13],[13,13],[17,2],[13,11],[4,6],[7,7],[10,3],[1,3],[20,18],[11,2],[8,7],[1,13],[4,16],[14,16],[2,10],[1,14],[5,7],[3,12],[2,16]]";

        // (?<=]),(?=\[) 正则表达式含义是：找这样一个逗号，前面跟着]，后面跟着[
        // 其中(?<=) 表示前面跟着
        // 其中(?=) 表示后面跟着
        int[][] books = Arrays.stream(input.substring(1, input.length() - 1).split("(?<=]),(?=\\[)"))
                .map(s -> Arrays.stream(s.substring(1, s.length() - 1).split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(books));
        System.out.println(getResult2(books));
    }

    /**
     * <a href="https://leetcode.cn/problems/longest-increasing-subsequence/solutions/14796/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/">耐心排序讲解</a>
     *
     * @param books
     * @return
     */
    public static int getResult(int[][] books) {
        // 长度升序，若长度相同，则宽度降序(逆序排序+保证在 长度 相同的数对中最多只选取一个)
        Arrays.sort(books, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] widths = Arrays.stream(books)
                .mapToInt(book -> book[1])
                .toArray();
        return new Leetcode300().patientSort(widths); // 两级排序 配合 递增子序列 实现 长度相同的数对中最多只选取一个
    }

    /**
     * 动态规划(参考最长递增子序列 - Leetcode300)
     * leetcode测试不通过，超出时间限制
     *
     * @param books
     * @return
     */
    public static int getResult2(int[][] books) {
        // 两级排序 长度升序，若长度相同，则宽度降序
        Arrays.sort(books, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
        int[] dp = new int[books.length];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 1; i < books.length; i++) {
            for (int j = 0; j < i; j++) {
                if (books[i][1] > books[j][1]) { // 两级排序 配合 递增子序列 实现 长度相同的数对中最多只选取一个
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }
}
